import java.util.ArrayList;
import java.util.List;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-15
 * Time:11:55
 */
/**1380. 矩阵中的幸运数
 * 给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。
 *
 * 幸运数是指矩阵中满足同时下列两个条件的元素：
 *
 * 在同一行的所有元素中最小
 * 在同一列的所有元素中最大
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/lucky-numbers-in-a-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class TestDemo {
    public static List<Integer> luckyNumbers(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            int min = Integer.MAX_VALUE;
            int r = -1;
            int l = -1;
            for (int j = 0; j < matrix[0].length; j++) {
                //找到每行的最小值并且记录其行和列
                if (matrix[i][j] < min) {
                    min = matrix[i][j];
                    r = i;
                    l = j;
                }
                //当进行到每行最后一列时 判断改行的最小值是否为该列的最大值
                if (j == matrix[0].length - 1) {
                    boolean flag = true;
                    //遍历每一行最小值的对应列
                    for (int k = 0; k < matrix.length ; k++) {
                        if (matrix[k][l] > min && k != r) {
                           flag = false;
                           break;
                        }
                    }
                    if (flag) {
                        list.add(min);
                    }
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,10,4,2},{9,3,8,7},{15,16,17,12}};
        System.out.println(luckyNumbers(matrix));
    }
}
